283. 移动零

#leetcode/pointer/fast-slow

283. 移动零

Similar Question

leading to the advanced question

Solution Tips

方案一: 快慢指针

这种方法与上面的工作方式相同，即先满足一个需求，然后满足另一个需求。它以一种巧妙的方式做到了这一点。上述问题也可以用另一种方式描述，“将所有非 0 元素置于数组前面，保持它们的相对顺序相同”

这是双指针的方法。由变量 “cur” 表示的快速指针负责处理新元素

  1. 如果新找到的元素不是 0，我们就在最后找到的非 0 元素之后记录它。最后找到的非 0 元素的位置由慢指针 “lastNonZero” 变量表示
  2. 当我们不断发现新的非 0 元素时，我们只是在第 “lastNonZero+1” 个索引处覆盖它们。此覆盖不会导致任何数据丢失，因为我们已经处理了其中的内容（如果它是非 0 的，则它现在已经写入了相应的索引，或者如果它是 0，则稍后将进行处理）

在 “cur” 索引到达数组的末尾之后，我们现在知道所有非 0 元素都已按原始顺序移动到数组的开头。现在是时候满足其他要求了，“将所有 0 移动到末尾”。我们现在只需要从 “lastNonZero+1” 索引开始用 0 填充所有索引。

  var moveZeroes = function (nums) {
    let lastNonZero = -1;
    for (let i = 0; i < nums.length; i++) {
      if (nums[i] !== 0) nums[++lastNonZero] = nums[i];
    }
	// 末尾填充 0
    for (let i = lastNonZero + 1; i < nums.length; i++) {
      nums[i] = 0;
    }
    return nums;
  };
  let nums = [0, 1, 0, 3, 12];
	
  console.log(moveZeroes(nums));

方案二: 两个 for 循环一起处理

前一种方法的操作是局部优化的。例如，所有（除最后一个）前导零的数组：[0，0，0，…，0，1]。对数组执行多少写操作？对于前面的方法，它写 0 n−1 次，这是不必要的。我们本可以只写一次。怎么用？… 只需固定非 0 元素。

最优方法也是上述解决方案的一个细微扩展。一个简单的实现是，如果当前元素是非 0 的，那么它的正确位置最多可以是当前位置或者更早的位置。如果是后者，则当前位置最终将被非 0 或 0 占据，该非 0 或 0 位于大于 “cur” 索引的索引处。我们马上用 0 填充当前位置，这样不像以前的解决方案，我们不需要在下一个迭代中回到这里。

换句话说，代码将保持以下不变：

  1. 慢指针（lastNonZero）之前的所有元素都是非零的。
  2. 当前指针和慢速指针之间的所有元素都是零。

因此，当我们遇到一个非零元素时，我们需要交换当前指针和慢速指针指向的元素，然后前进两个指针。如果它是零元素，我们只前进当前指针。

  var moveZeroes = function (nums) {
    let lastNonZero = -1;
    for (let i = 0; i < nums.length; i++) {
      if (nums[i] !== 0) {
        lastNonZero++;
        [nums[lastNonZero], nums[i]] = [nums[i], nums[lastNonZero]];
      }
    }
    return nums;
  };